class Solution:
    # @param grid, a list of list of characters
    # @return an integer
    def numIslands(self, grid):
    	rows = len(grid)
    	if rows == 0:
    		return 0
    	cols = len(grid[0])
    	if cols == 0:
    		return 0
    	for line in grid:
    		line.insert(0,'0')
    		line.append('0')
    	grid.insert(0,['0' for i in xrange(cols+2)])
    	grid.append(['0' for i in xrange(cols+2)])
    	rows += 2
    	cols += 2
    	count = 0
    	dire_r = [-1, 0, 1, 0]
    	dire_c = [0, 1, 0, -1]
    	for i in xrange(1, rows-1):
    		for j in xrange(1, cols-1):
    			if grid[i][j] == '1':
    				count += 1
    				que = [(i,j)]
    				while len(que) > 0:
    					tpoint = que.pop()
    					grid[tpoint[0]][tpoint[1]] = None
    					for d in xrange(4):
    						ti, tj = tpoint[0]+dire_r[d], tpoint[1]+dire_c[d]
    						if grid[ti][tj] == '1':
    							que.append((ti,tj))
    	return count

if __name__ == '__main__':
	so = Solution()
	g = [
		['1','1','0','0','0'],
		['1','1','0','0','0'],
		['0','0','1','0','0'],
		['0','0','0','1','1']
	]
	print so.numIslands(g)